import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2025-03-07
 * Time: 23:00
 */
public class Main {
    //自己写的第一版
    public List<List<Integer>> threeSum1(int[] nums) {
        Arrays.sort(nums);

        int n = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i != 0 && nums[i]==nums[i-1] ){
                continue;
            }

            int left = i+1;
            int right = n-1;

            while (left < right){
                if (nums[left] == nums[left+1]){
                    left++;
                }
                if (nums[right] == nums[right-1]){
                    right--;
                }
                if (nums[left] + nums[right] + nums[i] > 0){
                    right--;
                }else if (nums[left] + nums[right] +nums[i] < 0){
                    left++;
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    left++;
                    right--;
                }
            }

        }
        return lists;
    }

    //kimi改的
    public List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);

        int n = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i != 0 && nums[i]==nums[i-1] ){
                continue;
            }

            int left = i+1;
            int right = n-1;

            while (left < right){

                if (nums[left] + nums[right] + nums[i] > 0){
                    right--;
                }else if (nums[left] + nums[right] +nums[i] < 0){
                    left++;
                }else {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);

                    while (left < right && nums[left] == nums[left+1] ){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right-1]){
                        right--;
                    }

                    left++;
                    right--;
                }
            }

        }
        return lists;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();

        //1.排序
        Arrays.sort(nums);

        //2.利用双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n;) { // 固定数a
            if (nums[i] > 0){
                break;//小优化
            }
            int left = i + 1,right = n - 1,target = -nums[i];
            while (left < right){
                int sum = nums[left] + nums[right];
                if (sum > target){
                    right--;
                }else if (sum < target){
                    left++;
                }else {
                    //nums[i] nums[left] nums[right]
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;right--;

                    //去重
                    while (left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right+1]){
                        right--;
                    }
                }
            }
            i++;
            //去重i
            while (i < n && nums[i] == nums[i - 1]){
                i++;
            }
        }
        return ret;
    }

}
